//
// Created by xili on 2024/9/10 10:04.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int maxSizeSlices(vector<int> &slices) {
        int n = slices.size();
        int m = n / 3; // 需要取的披萨块数
        // dp[i][j] 表示前 i 个披萨中选择 j 块能获得的最大值
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = max(dp[i - 1][j], (i >= 2 ? dp[i - 2][j - 1] : 0) + slices[i - 1]);
            }
        }
        // 分别考虑去掉第一个和最后一个元素，求最大值
        int res1 = dp[n - 1][m];
        // 重新初始化 dp 数组
        fill(dp.begin(), dp.end(), vector<int>(m + 1, 0));

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = max(dp[i - 1][j], (i >= 2 ? dp[i - 2][j - 1] : 0) + slices[i - 1]);
            }
        }
        int res2 = dp[n][m];

        return max(res1, res2);
    }
};
;